package com.example.arithmeticleetcode.learnArithmetic2.greedy;

import java.util.Arrays;

/**
 * @program: arithmetic-leetcode
 * @description: 贪心策略不一定得到全局最优解 但是简单，高效，可以当做其他算法的辅助算法
 * @author: FangZhen
 * @create: 2020-12-11 10:26
 **/
public class Pirate {

    public static void main(String[] args) {
        Integer[] faces = {25, 20, 5, 1};
        int money = 41;
        coinChange(faces, money);

        System.out.println("-------------------");
        teacherChooseSmallCoins(faces, money);
        System.out.println("-----------------------");
        chooseSmallCountCoin(faces, money);
    }

    private static void coinChange(Integer[] faces, int money) {
        Arrays.sort(faces, (f1, f2) ->  f2 - f1);
        int coins = 0, i = 0;
        while (i < faces.length) {
            if (money < faces[i]) {
                i++;
                continue;
            }
            System.out.print(faces[i] + " ");
            money -= faces[i];
            coins++;
        }
        System.out.println(System.lineSeparator() + coins);
    }

    /**
     * 老师零钱找零，找最小数量的零钱，每个零钱可以重复
     */
    private static void teacherChooseSmallCoins(Integer[] faces, int money) {
        Arrays.sort(faces);
        int coins = 0;
        for (int i = faces.length - 1; i >= 0; i--) {
            if (money < faces[i]) {
                continue;
            }
            System.out.print(faces[i] + " ");
            money -= faces[i];
            coins++;
            i = faces.length;

        }
        System.out.println(System.lineSeparator() + coins);
    }

    /**
     * 零钱找零，找最小数量的零钱，每个零钱可以重复
     */
    private static void chooseSmallCountCoin(Integer[] faces, int money) {
        Arrays.sort(faces);
        int coins = 0;
        for (int i = faces.length - 1; i >= 0; i--) {
            if (money < faces[i]) {
                continue;
            }

            int count = money / faces[i];
            coins += count;
            money -= faces[i] * count;
            System.out.print(faces[i] + "====" + count + "  ");
        }
        System.out.println(System.lineSeparator() + coins);
    }


    /**
     * 简单的贪心计算 加勒比海盗能装最大数量的古董 每个古董只能选一次,且只有一件古董
     */
    private static void greedy01() {
        int[] weights = {3, 5, 4, 10, 7, 14, 2, 11};
        Arrays.sort(weights);
        int capacity = 30;
        int weight = 0;
        int count = 0;
        for (int i = 0; i < weights.length && weight < capacity; i++) {
            weight += weights[i];
            if (weight <= capacity) {
                System.out.print(weights[i] + " ");
                count++;
            }
        }
        System.out.println(System.lineSeparator() + count);
    }
}
